class Solution {
    public:
        // 白色最少 == 黑色最多
        int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
            int n = floor.size();
            // 记忆化搜索
            vector memo(n + 1, vector<int>(numCarpets + 1, -1));
            auto dfs = [&](this auto&& dfs, int x, int y) {
                // 有y块地毯和x块砖，求对应的黑色最大值
                if (x <= y * carpetLen) {
                    // 铺满了
                    return 0;
                }
                int& res = memo[x - 1][y];
                if (res != -1) {
                    // 记忆化搜索
                    return res;
                }
                // if (floor[x - 1] == '0') {
                //     // 遇到黑色
                //     return res = dfs( x - 1, y);
                // }
                return res =
                           min((y > 0 ? dfs(x - carpetLen, y - 1) : INT_MAX),
                               dfs(x - 1, y) + (floor[x - 1] - '0'));
            };
            return dfs(n, numCarpets);
        }
    };

                